{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximize Grid Happiness"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #memoization #dynamic-programming #bitmask"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #记忆化搜索 #动态规划 #状态压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getMaxGridHappiness"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大化网格幸福感"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你四个整数 <code>m</code>、<code>n</code>、<code>introvertsCount</code> 和 <code>extrovertsCount</code> 。有一个 <code>m x n</code> 网格，和两种类型的人：内向的人和外向的人。总共有 <code>introvertsCount</code> 个内向的人和 <code>extrovertsCount</code> 个外向的人。</p>\n",
    "\n",
    "<p>请你决定网格中应当居住多少人，并为每个人分配一个网格单元。 注意，<strong>不必</strong> 让所有人都生活在网格中。</p>\n",
    "\n",
    "<p>每个人的 <strong>幸福感</strong> 计算如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>内向的人 <strong>开始</strong> 时有 <code>120</code> 个幸福感，但每存在一个邻居（内向的或外向的）他都会 <strong>失去</strong>  <code>30</code> 个幸福感。</li>\n",
    "\t<li>外向的人 <strong>开始</strong> 时有 <code>40</code> 个幸福感，每存在一个邻居（内向的或外向的）他都会 <strong>得到</strong>  <code>20</code> 个幸福感。</li>\n",
    "</ul>\n",
    "\n",
    "<p>邻居是指居住在一个人所在单元的上、下、左、右四个直接相邻的单元中的其他人。</p>\n",
    "\n",
    "<p><strong>网格幸福感</strong> 是每个人幸福感的 <strong>总和</strong> 。 返回 <strong>最大可能的网格幸福感</strong> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/11/15/grid_happiness.png\" style=\"width: 261px; height: 121px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>m = 2, n = 3, introvertsCount = 1, extrovertsCount = 2\n",
    "<strong>输出：</strong>240\n",
    "<strong>解释：</strong>假设网格坐标 (row, column) 从 1 开始编号。\n",
    "将内向的人放置在单元 (1,1) ，将外向的人放置在单元 (1,3) 和 (2,3) 。\n",
    "- 位于 (1,1) 的内向的人的幸福感：120（初始幸福感）- (0 * 30)（0 位邻居）= 120\n",
    "- 位于 (1,3) 的外向的人的幸福感：40（初始幸福感）+ (1 * 20)（1 位邻居）= 60\n",
    "- 位于 (2,3) 的外向的人的幸福感：40（初始幸福感）+ (1 * 20)（1 位邻居）= 60\n",
    "网格幸福感为：120 + 60 + 60 = 240\n",
    "上图展示该示例对应网格中每个人的幸福感。内向的人在浅绿色单元中，而外向的人在浅紫色单元中。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>m = 3, n = 1, introvertsCount = 2, extrovertsCount = 1\n",
    "<strong>输出：</strong>260\n",
    "<strong>解释：</strong>将内向的人放置在单元 (1,1) 和 (3,1) ，将外向的人放置在单元 (2,1) 。\n",
    "- 位于 (1,1) 的内向的人的幸福感：120（初始幸福感）- (1 * 30)（1 位邻居）= 90\n",
    "- 位于 (2,1) 的外向的人的幸福感：40（初始幸福感）+ (2 * 20)（2 位邻居）= 80\n",
    "- 位于 (3,1) 的内向的人的幸福感：120（初始幸福感）- (1 * 30)（1 位邻居）= 90\n",
    "网格幸福感为 90 + 80 + 90 = 260\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>m = 2, n = 2, introvertsCount = 4, extrovertsCount = 0\n",
    "<strong>输出：</strong>240\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= m, n <= 5</code></li>\n",
    "\t<li><code>0 <= introvertsCount, extrovertsCount <= min(m * n, 6)</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximize-grid-happiness](https://leetcode.cn/problems/maximize-grid-happiness/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximize-grid-happiness](https://leetcode.cn/problems/maximize-grid-happiness/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2\\n3\\n1\\n2', '3\\n1\\n2\\n1', '2\\n2\\n4\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxGridHappiness(self, m: int, n: int, ic: int, ec: int) -> int:\n",
    "        \n",
    "        # def check(x, y, imask, emask):\n",
    "        #     for dx, dy in [(0, -1), (-1, 0)]:\n",
    "        #         nx, ny = x + dx, y + dy\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dp(ic, ec, prev, idx):\n",
    "            if ic < 0 or ec < 0:\n",
    "                return float('-inf')\n",
    "            if idx == m * n:\n",
    "                return 0\n",
    "            x, y = idx // n, idx % n\n",
    "            nei_i, nei_e = 0, 0\n",
    "            if y > 0:\n",
    "                nei_i += int(prev[-1] == 1)\n",
    "                nei_e += int(prev[-1] == 2)\n",
    "            if x > 0:\n",
    "                nei_i += int(prev[0] == 1)\n",
    "                nei_e += int(prev[0] == 2)\n",
    "            return max(120 - 30 *(nei_e + nei_i * 2) + 20 * nei_e + dp(ic-1,ec,prev[1:]+(1,), idx+1),\n",
    "                       40 + 20 * (nei_e * 2 + nei_i) - 30 * nei_i + dp(ic, ec-1,prev[1:]+(2,), idx+1),\n",
    "                       dp(ic, ec, prev[1:]+(0,), idx+1))\n",
    "        \n",
    "        return dp(ic, ec, tuple([0]*n), 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxGridHappiness(self, m: int, n: int, introvertsCount: int, extrovertsCount: int) -> int:\n",
    "        offset = [[0, 0, 0], [0, - 60, - 10], [0, - 10, 40]]\n",
    "        case = pow(3, n)\n",
    "        base = pow(3, n - 1)\n",
    "        dp = [[[- float('inf') for _ in range(extrovertsCount + 1)] for _ in range(introvertsCount + 1)] for _ in range(case)]\n",
    "        dp[0][0][0] = 0\n",
    "        for coor in range(m * n):\n",
    "            new = [[[- float('inf') for _ in range(extrovertsCount + 1)] for _ in range(introvertsCount + 1)] for _ in range(case)]\n",
    "            i, j = coor // n, coor % n \n",
    "            for cur in range(case):\n",
    "                left = cur % 3 \n",
    "                up = cur // base\n",
    "                nxt = cur * 3 % case \n",
    "                for intro in range(introvertsCount + 1):\n",
    "                    for extro in range(extrovertsCount + 1):\n",
    "                        if intro < introvertsCount:\n",
    "                            new[nxt + 1][intro + 1][extro] = max(new[nxt + 1][intro + 1][extro], dp[cur][intro][extro] + (j != 0) * offset[1][left] + (i != 0) * offset[1][up] + 120)\n",
    "                        if extro < extrovertsCount:\n",
    "                            new[nxt + 2][intro][extro + 1] = max(new[nxt + 2][intro][extro + 1], dp[cur][intro][extro] + (j != 0) * offset[2][left] + (i != 0) * offset[2][up] + 40)\n",
    "                        new[nxt + 0][intro][extro] = max(new[nxt + 0][intro][extro], dp[cur][intro][extro])\n",
    "            dp = new \n",
    "       \n",
    "        res = - float('inf')\n",
    "        for i in range(case):\n",
    "            for j in range(introvertsCount + 1):\n",
    "                for k in range(extrovertsCount + 1):\n",
    "                    res = max(res, dp[i][j][k])\n",
    "        return res\n",
    "                        \n",
    "                           \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxGridHappiness(self, m: int, n: int, introvertsCount: int, extrovertsCount: int) -> int:\n",
    "        dfs = [[0, 0, 0]]\n",
    "        edgebfs = {}\n",
    "        all=introvertsCount+extrovertsCount\n",
    "        ans=0\n",
    "        while dfs:\n",
    "            cur = dfs.pop()\n",
    "            # score = cur[0]\n",
    "            icnt = cur[1]\n",
    "            ecnt = cur[2]\n",
    "            if len(cur) < n + 3:\n",
    "                dfs.append(cur + [0])\n",
    "                if icnt < introvertsCount:\n",
    "                    ncur = list(cur)\n",
    "                    ncur[1] += 1\n",
    "                    ncur[0] += 120\n",
    "                    if len(cur) > 3 and cur[-1] != 0:\n",
    "                        if cur[-1] == 1:\n",
    "                            ncur[0] -= 60\n",
    "                        else:\n",
    "                            ncur[0] -= 10\n",
    "                    if ncur[1]+ncur[2]==all:\n",
    "                        ans=max(ans,ncur[0])\n",
    "                    else:\n",
    "                        dfs.append(ncur + [1])\n",
    "                if ecnt < extrovertsCount:\n",
    "                    ncur = list(cur)\n",
    "                    ncur[2] += 1\n",
    "                    ncur[0] += 40\n",
    "                    if len(cur) > 3 and cur[-1] != 0:\n",
    "                        if cur[-1] == 1:\n",
    "                            ncur[0]-= 10\n",
    "                        else:\n",
    "                            ncur[0]+= 40\n",
    "                    if ncur[1]+ncur[2]==all:\n",
    "                        ans=max(ans,ncur[0])\n",
    "                    else:\n",
    "                        dfs.append(ncur + [2])\n",
    "            else:\n",
    "                cedge = '-'.join([str(x) for x in cur[1:]])\n",
    "                edgebfs[cedge] = cur[0]\n",
    "\n",
    "        for r in range(1, m):\n",
    "            for c in range(n):\n",
    "                nbfs = {}\n",
    "                for k, v in edgebfs.items():\n",
    "                    sk = [int(x) for x in k.split('-')]\n",
    "                    icnt = sk[0]\n",
    "                    ecnt = sk[1]\n",
    "                    nsk = list(sk)\n",
    "                    nsk[c + 2] = 0\n",
    "                    nedge = '-'.join([str(x) for x in nsk])\n",
    "                    if nedge not in nbfs:\n",
    "                        nbfs[nedge] = v\n",
    "                    else:\n",
    "                        if v > nbfs[nedge]:\n",
    "                            nbfs[nedge] = v\n",
    "                    if icnt < introvertsCount:\n",
    "                        nsk = list(sk)\n",
    "                        nsk[0] += 1\n",
    "                        nsk[c + 2] = 1\n",
    "                        cv = v\n",
    "                        cv += 120\n",
    "                        if sk[c + 2] == 1:\n",
    "                            cv -= 60\n",
    "                        elif sk[c + 2] == 2:\n",
    "                            cv -= 10\n",
    "                        if c > 0:\n",
    "                            if sk[c + 1] == 1:\n",
    "                                cv -= 60\n",
    "                            elif sk[c + 1] == 2:\n",
    "                                cv -= 10\n",
    "                        if nsk[0]+nsk[1]==all:\n",
    "                            ans=max(ans,cv)\n",
    "                        else:\n",
    "                            nedge = '-'.join([str(x) for x in nsk])\n",
    "                            if nedge not in nbfs:\n",
    "                                nbfs[nedge] = cv\n",
    "                            else:\n",
    "                                if cv > nbfs[nedge]:\n",
    "                                    nbfs[nedge] = cv\n",
    "                    if ecnt < extrovertsCount:\n",
    "                        nsk = list(sk)\n",
    "                        nsk[1] += 1\n",
    "                        nsk[c + 2] = 2\n",
    "                        cv = v\n",
    "                        cv += 40\n",
    "                        if sk[c + 2] == 1:\n",
    "                            cv -= 10\n",
    "                        elif sk[c + 2] == 2:\n",
    "                            cv += 40\n",
    "                        if c > 0:\n",
    "                            if sk[c + 1] == 1:\n",
    "                                cv -= 10\n",
    "                            elif sk[c + 1] == 2:\n",
    "                                cv += 40\n",
    "                        if nsk[0] + nsk[1] == all:\n",
    "                            ans = max(ans, cv)\n",
    "                        else:\n",
    "                            nedge = '-'.join([str(x) for x in nsk])\n",
    "                            if nedge not in nbfs:\n",
    "                                nbfs[nedge] = cv\n",
    "                            else:\n",
    "                                if cv > nbfs[nedge]:\n",
    "                                    nbfs[nedge] = cv\n",
    "                edgebfs = nbfs\n",
    "\n",
    "        return max(ans,max(edgebfs.values()))\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    T = 243\n",
    "    N = 5\n",
    "    M = 6\n",
    "    score = [\n",
    "        [0, 0, 0],\n",
    "        [0, -60, -10],\n",
    "        [0, -10, 40]\n",
    "    ]\n",
    "\n",
    "    def __init__(self):\n",
    "        self.mask_bits = [[0] * Solution.N for _ in range(Solution.T)]\n",
    "        self.iv_count = [0] * Solution.T\n",
    "        self.ev_count = [0] * Solution.T\n",
    "        self.inner_score = [0] * Solution.T\n",
    "        self.inter_score = [[0] * Solution.T for _ in range(Solution.T)]\n",
    "        self.d = [[[[-1] * (Solution.M + 1) for _ in range(Solution.M + 1)] for _ in range(Solution.T)] for _ in range(Solution.N)]\n",
    "\n",
    "    def init_data(self):\n",
    "        for mask in range(self.tot):\n",
    "            mask_tmp = mask\n",
    "            for i in range(self.n):\n",
    "                x = mask_tmp % 3\n",
    "                self.mask_bits[mask][i] = x\n",
    "                mask_tmp //= 3\n",
    "                if x == 1:\n",
    "                    self.iv_count[mask] += 1\n",
    "                    self.inner_score[mask] += 120\n",
    "                elif x == 2:\n",
    "                    self.ev_count[mask] += 1\n",
    "                    self.inner_score[mask] += 40\n",
    "                if i > 0:\n",
    "                    self.inner_score[mask] += Solution.score[x][self.mask_bits[mask][i - 1]]\n",
    "\n",
    "        for i in range(self.tot):\n",
    "            for j in range(self.tot):\n",
    "                for k in range(self.n):\n",
    "                    self.inter_score[i][j] += Solution.score[self.mask_bits[i][k]][self.mask_bits[j][k]]\n",
    "\n",
    "    def getMaxGridHappiness(self, m: int, n: int, introvertsCount: int, extrovertsCount: int) -> int:\n",
    "        self.n = n\n",
    "        self.m = m\n",
    "        self.tot = 3**n\n",
    "        self.init_data()\n",
    "        return self.dfs(0, 0, introvertsCount, extrovertsCount)\n",
    "\n",
    "    def dfs(self, row: int, premask: int, iv: int, ev: int) -> int:\n",
    "        if row == self.m or (iv == 0 and ev == 0):\n",
    "            return 0\n",
    "\n",
    "        if self.d[row][premask][iv][ev] != -1:\n",
    "            return self.d[row][premask][iv][ev]\n",
    "\n",
    "        res = 0\n",
    "        for mask in range(self.tot):\n",
    "            if self.iv_count[mask] > iv or self.ev_count[mask] > ev:\n",
    "                continue\n",
    "            res = max(res, \n",
    "                      self.dfs(row + 1, mask, iv - self.iv_count[mask], ev - self.ev_count[mask]) \n",
    "                      + self.inner_score[mask] \n",
    "                      + self.inter_score[premask][mask])\n",
    "        \n",
    "        self.d[row][premask][iv][ev] = res\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxGridHappiness(self, m: int, n: int, introvertsCount: int, extrovertsCount: int) -> int:\n",
    "        T, N, M = 243, 5, 6\n",
    "        # 邻居间的分数\n",
    "        score = [\n",
    "            [0, 0, 0],\n",
    "            [0, -60, -10],\n",
    "            [0, -10, 40],\n",
    "        ]\n",
    "\n",
    "        tot = 3**n\n",
    "        mask_bits = [[0] * N for _ in range(T)]\n",
    "        iv_count, ev_count = [0] * T, [0] * T\n",
    "        inner_score = [0] * T\n",
    "        inter_score = [[0] * T for _ in range(T)]\n",
    "    \n",
    "        def init_data() -> None:\n",
    "            # 计算行内分数\n",
    "            for mask in range(tot):\n",
    "                mask_tmp = mask\n",
    "                for i in range(n):\n",
    "                    x = mask_tmp % 3\n",
    "                    mask_bits[mask][i] = x\n",
    "                    mask_tmp //= 3\n",
    "                    if x == 1:\n",
    "                        iv_count[mask] += 1\n",
    "                        inner_score[mask] += 120\n",
    "                    elif x == 2:\n",
    "                        ev_count[mask] += 1\n",
    "                        inner_score[mask] += 40\n",
    "                    if i > 0:\n",
    "                        inner_score[mask] += score[x][mask_bits[mask][i - 1]]\n",
    "            # 计算行间分数\n",
    "            for i in range(tot):\n",
    "                for j in range(tot):\n",
    "                    for k in range(n):\n",
    "                        inter_score[i][j] += score[mask_bits[i][k]][mask_bits[j][k]]\n",
    "        \n",
    "        @cache\n",
    "        def dfs(row: int, premask: int, iv: int, ev: int) -> int:\n",
    "            if row == m or (iv == 0 and ev == 0):\n",
    "                return 0\n",
    "            \n",
    "            res = 0\n",
    "            for mask in range(tot):\n",
    "                # mask 包含的内向人数不能超过 iv ，外向人数不能超过 ev\n",
    "                if iv_count[mask] > iv or ev_count[mask] > ev:\n",
    "                    continue\n",
    "                res = max(res, dfs(row + 1, mask, iv - iv_count[mask], ev - ev_count[mask]) + inner_score[mask] + inter_score[premask][mask])\n",
    "            return res\n",
    "\n",
    "        init_data()\n",
    "        return dfs(0, 0, introvertsCount, extrovertsCount)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxGridHappiness(self, m: int, n: int, introvertsCount: int, extrovertsCount: int) -> int:\n",
    "        T,N,M = 243,5,6\n",
    "        score = [\n",
    "            [0,0,0],\n",
    "            [0,-60,-10],\n",
    "            [0,-10,40]\n",
    "        ]\n",
    "\n",
    "        tot = 3 ** n \n",
    "        mask_bits = [[0] * N for _ in range(T)]\n",
    "        iv_count,ev_count = [0] * T ,[0] * T \n",
    "        inner_score = [0] * T \n",
    "        inter_score = [[0] * T for _ in range(T)]\n",
    "\n",
    "        def init_data():\n",
    "            for mask in range(tot):\n",
    "                mask_tmp = mask\n",
    "                for i in range(n):\n",
    "                    x = mask_tmp % 3 \n",
    "                    mask_bits[mask][i] = x\n",
    "                    mask_tmp //= 3\n",
    "                    if x == 1:\n",
    "                        iv_count[mask] += 1\n",
    "                        inner_score[mask] += 120\n",
    "                    elif x == 2:\n",
    "                        ev_count[mask] += 1\n",
    "                        inner_score[mask] += 40\n",
    "                    if i > 0:\n",
    "                        inner_score[mask] += score[x][mask_bits[mask][i - 1]]\n",
    "            # 计算行间分数\n",
    "            for i in range(tot):\n",
    "                for j in range(tot):\n",
    "                    for k in range(n):\n",
    "                        inter_score[i][j] += score[mask_bits[i][k]][mask_bits[j][k]]\n",
    "        \n",
    "        @cache\n",
    "        def dfs(row: int, premask: int, iv: int, ev: int) -> int:\n",
    "            if row == m or (iv == 0 and ev == 0):\n",
    "                return 0\n",
    "            \n",
    "            res = 0\n",
    "            for mask in range(tot):\n",
    "                # mask 包含的内向人数不能超过 iv ，外向人数不能超过 ev\n",
    "                if iv_count[mask] > iv or ev_count[mask] > ev:\n",
    "                    continue\n",
    "                res = max(res, dfs(row + 1, mask, iv - iv_count[mask], ev - ev_count[mask]) + inner_score[mask] + inter_score[premask][mask])\n",
    "            return res\n",
    "\n",
    "        init_data()\n",
    "        return dfs(0, 0, introvertsCount, extrovertsCount)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxGridHappiness(self, m: int, n: int, introvertsCount: int, extrovertsCount: int) -> int:\n",
    "        T, N, M = 243, 5, 6\n",
    "        # 邻居间的分数\n",
    "        score = [\n",
    "            [0, 0, 0],\n",
    "            [0, -60, -10],\n",
    "            [0, -10, 40],\n",
    "        ]\n",
    "\n",
    "        tot = 3**n\n",
    "        mask_bits = [[0] * N for _ in range(T)]\n",
    "        iv_count, ev_count = [0] * T, [0] * T\n",
    "        inner_score = [0] * T\n",
    "        inter_score = [[0] * T for _ in range(T)]\n",
    "    \n",
    "        def init_data() -> None:\n",
    "            # 计算行内分数\n",
    "            for mask in range(tot):\n",
    "                mask_tmp = mask\n",
    "                for i in range(n):\n",
    "                    x = mask_tmp % 3\n",
    "                    mask_bits[mask][i] = x\n",
    "                    mask_tmp //= 3\n",
    "                    if x == 1:\n",
    "                        iv_count[mask] += 1\n",
    "                        inner_score[mask] += 120\n",
    "                    elif x == 2:\n",
    "                        ev_count[mask] += 1\n",
    "                        inner_score[mask] += 40\n",
    "                    if i > 0:\n",
    "                        inner_score[mask] += score[x][mask_bits[mask][i - 1]]\n",
    "            # 计算行间分数\n",
    "            for i in range(tot):\n",
    "                for j in range(tot):\n",
    "                    for k in range(n):\n",
    "                        inter_score[i][j] += score[mask_bits[i][k]][mask_bits[j][k]]\n",
    "        \n",
    "        @cache\n",
    "        def dfs(row: int, premask: int, iv: int, ev: int) -> int:\n",
    "            if row == m or (iv == 0 and ev == 0):\n",
    "                return 0\n",
    "            \n",
    "            res = 0\n",
    "            for mask in range(tot):\n",
    "                # mask 包含的内向人数不能超过 iv ，外向人数不能超过 ev\n",
    "                if iv_count[mask] > iv or ev_count[mask] > ev:\n",
    "                    continue\n",
    "                res = max(res, dfs(row + 1, mask, iv - iv_count[mask], ev - ev_count[mask]) + inner_score[mask] + inter_score[premask][mask])\n",
    "            return res\n",
    "\n",
    "        init_data()\n",
    "        return dfs(0, 0, introvertsCount, extrovertsCount)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxGridHappiness(self, m: int, n: int, introvertsCount: int, extrovertsCount: int) -> int:\n",
    "        T, N, M = 243, 5, 6\n",
    "        # 邻居间的分数\n",
    "        score = [\n",
    "            [0, 0, 0],\n",
    "            [0, -60, -10],\n",
    "            [0, -10, 40],\n",
    "        ]\n",
    "\n",
    "        tot = 3**n\n",
    "        mask_bits = [[0] * N for _ in range(T)]\n",
    "        iv_count, ev_count = [0] * T, [0] * T\n",
    "        inner_score = [0] * T\n",
    "        inter_score = [[0] * T for _ in range(T)]\n",
    "    \n",
    "        def init_data() -> None:\n",
    "            # 计算行内分数\n",
    "            for mask in range(tot):\n",
    "                mask_tmp = mask\n",
    "                for i in range(n):\n",
    "                    x = mask_tmp % 3\n",
    "                    mask_bits[mask][i] = x\n",
    "                    mask_tmp //= 3\n",
    "                    if x == 1:\n",
    "                        iv_count[mask] += 1\n",
    "                        inner_score[mask] += 120\n",
    "                    elif x == 2:\n",
    "                        ev_count[mask] += 1\n",
    "                        inner_score[mask] += 40\n",
    "                    if i > 0:\n",
    "                        inner_score[mask] += score[x][mask_bits[mask][i - 1]]\n",
    "            # 计算行间分数\n",
    "            for i in range(tot):\n",
    "                for j in range(tot):\n",
    "                    for k in range(n):\n",
    "                        inter_score[i][j] += score[mask_bits[i][k]][mask_bits[j][k]]\n",
    "        \n",
    "        @cache\n",
    "        def dfs(row: int, premask: int, iv: int, ev: int) -> int:\n",
    "            if row == m or (iv == 0 and ev == 0):\n",
    "                return 0\n",
    "            \n",
    "            res = 0\n",
    "            for mask in range(tot):\n",
    "                # mask 包含的内向人数不能超过 iv ，外向人数不能超过 ev\n",
    "                if iv_count[mask] > iv or ev_count[mask] > ev:\n",
    "                    continue\n",
    "                res = max(res, dfs(row + 1, mask, iv - iv_count[mask], ev - ev_count[mask]) + inner_score[mask] + inter_score[premask][mask])\n",
    "            return res\n",
    "\n",
    "        init_data()\n",
    "        return dfs(0, 0, introvertsCount, extrovertsCount)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxGridHappiness(self, m: int, n: int, introvertsCount: int, extrovertsCount: int) -> int:\n",
    "        T, N, M = 243, 5, 6\n",
    "        # 邻居间的分数\n",
    "        score = [\n",
    "            [0, 0, 0],\n",
    "            [0, -60, -10],\n",
    "            [0, -10, 40],\n",
    "        ]\n",
    "\n",
    "        tot = 3**n\n",
    "        mask_bits = [[0] * N for _ in range(T)]\n",
    "        iv_count, ev_count = [0] * T, [0] * T\n",
    "        inner_score = [0] * T\n",
    "        inter_score = [[0] * T for _ in range(T)]\n",
    "    \n",
    "        def init_data() -> None:\n",
    "            # 计算行内分数\n",
    "            for mask in range(tot):\n",
    "                mask_tmp = mask\n",
    "                for i in range(n):\n",
    "                    x = mask_tmp % 3\n",
    "                    mask_bits[mask][i] = x\n",
    "                    mask_tmp //= 3\n",
    "                    if x == 1:\n",
    "                        iv_count[mask] += 1\n",
    "                        inner_score[mask] += 120\n",
    "                    elif x == 2:\n",
    "                        ev_count[mask] += 1\n",
    "                        inner_score[mask] += 40\n",
    "                    if i > 0:\n",
    "                        inner_score[mask] += score[x][mask_bits[mask][i - 1]]\n",
    "            # 计算行间分数\n",
    "            for i in range(tot):\n",
    "                for j in range(tot):\n",
    "                    for k in range(n):\n",
    "                        inter_score[i][j] += score[mask_bits[i][k]][mask_bits[j][k]]\n",
    "        \n",
    "        @cache\n",
    "        def dfs(row: int, premask: int, iv: int, ev: int) -> int:\n",
    "            if row == m or (iv == 0 and ev == 0):\n",
    "                return 0\n",
    "            \n",
    "            res = 0\n",
    "            for mask in range(tot):\n",
    "                # mask 包含的内向人数不能超过 iv ，外向人数不能超过 ev\n",
    "                if iv_count[mask] > iv or ev_count[mask] > ev:\n",
    "                    continue\n",
    "                res = max(res, dfs(row + 1, mask, iv - iv_count[mask], ev - ev_count[mask]) + inner_score[mask] + inter_score[premask][mask])\n",
    "            return res\n",
    "\n",
    "        init_data()\n",
    "        return dfs(0, 0, introvertsCount, extrovertsCount)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxGridHappiness(self, m: int, n: int, introvertsCount: int, extrovertsCount: int) -> int:\n",
    "        T, N, M = 243, 5, 6\n",
    "        # 邻居间的分数\n",
    "        score = [\n",
    "            [0, 0, 0],\n",
    "            [0, -60, -10],\n",
    "            [0, -10, 40],\n",
    "        ]\n",
    "\n",
    "        tot = 3**n\n",
    "        mask_bits = [[0] * N for _ in range(T)]\n",
    "        iv_count, ev_count = [0] * T, [0] * T\n",
    "        inner_score = [0] * T\n",
    "        inter_score = [[0] * T for _ in range(T)]\n",
    "    \n",
    "        def init_data() -> None:\n",
    "            # 计算行内分数\n",
    "            for mask in range(tot):\n",
    "                mask_tmp = mask\n",
    "                for i in range(n):\n",
    "                    x = mask_tmp % 3\n",
    "                    mask_bits[mask][i] = x\n",
    "                    mask_tmp //= 3\n",
    "                    if x == 1:\n",
    "                        iv_count[mask] += 1\n",
    "                        inner_score[mask] += 120\n",
    "                    elif x == 2:\n",
    "                        ev_count[mask] += 1\n",
    "                        inner_score[mask] += 40\n",
    "                    if i > 0:\n",
    "                        inner_score[mask] += score[x][mask_bits[mask][i - 1]]\n",
    "            # 计算行间分数\n",
    "            for i in range(tot):\n",
    "                for j in range(tot):\n",
    "                    for k in range(n):\n",
    "                        inter_score[i][j] += score[mask_bits[i][k]][mask_bits[j][k]]\n",
    "        \n",
    "        @cache\n",
    "        def dfs(row: int, premask: int, iv: int, ev: int) -> int:\n",
    "            if row == m or (iv == 0 and ev == 0):\n",
    "                return 0\n",
    "            \n",
    "            res = 0\n",
    "            for mask in range(tot):\n",
    "                # mask 包含的内向人数不能超过 iv ，外向人数不能超过 ev\n",
    "                if iv_count[mask] > iv or ev_count[mask] > ev:\n",
    "                    continue\n",
    "                res = max(res, dfs(row + 1, mask, iv - iv_count[mask], ev - ev_count[mask]) + inner_score[mask] + inter_score[premask][mask])\n",
    "            return res\n",
    "\n",
    "        init_data()\n",
    "        return dfs(0, 0, introvertsCount, extrovertsCount)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxGridHappiness(self, m: int, n: int, introvertsCount: int, extrovertsCount: int) -> int:\n",
    "        T, N, M = 243, 5, 6\n",
    "        # 邻居间的分数\n",
    "        score = [\n",
    "            [0, 0, 0],\n",
    "            [0, -60, -10],\n",
    "            [0, -10, 40],\n",
    "        ]\n",
    "\n",
    "        tot = 3**n\n",
    "        mask_bits = [[0] * N for _ in range(T)]\n",
    "        iv_count, ev_count = [0] * T, [0] * T\n",
    "        inner_score = [0] * T\n",
    "        inter_score = [[0] * T for _ in range(T)]\n",
    "    \n",
    "        def init_data() -> None:\n",
    "            # 计算行内分数\n",
    "            for mask in range(tot):\n",
    "                mask_tmp = mask\n",
    "                for i in range(n):\n",
    "                    x = mask_tmp % 3\n",
    "                    mask_bits[mask][i] = x\n",
    "                    mask_tmp //= 3\n",
    "                    if x == 1:\n",
    "                        iv_count[mask] += 1\n",
    "                        inner_score[mask] += 120\n",
    "                    elif x == 2:\n",
    "                        ev_count[mask] += 1\n",
    "                        inner_score[mask] += 40\n",
    "                    if i > 0:\n",
    "                        inner_score[mask] += score[x][mask_bits[mask][i - 1]]\n",
    "            # 计算行间分数\n",
    "            for i in range(tot):\n",
    "                for j in range(tot):\n",
    "                    for k in range(n):\n",
    "                        inter_score[i][j] += score[mask_bits[i][k]][mask_bits[j][k]]\n",
    "        \n",
    "        @cache\n",
    "        def dfs(row: int, premask: int, iv: int, ev: int) -> int:\n",
    "            if row == m or (iv == 0 and ev == 0):\n",
    "                return 0\n",
    "            \n",
    "            res = 0\n",
    "            for mask in range(tot):\n",
    "                # mask 包含的内向人数不能超过 iv ，外向人数不能超过 ev\n",
    "                if iv_count[mask] > iv or ev_count[mask] > ev:\n",
    "                    continue\n",
    "                res = max(res, dfs(row + 1, mask, iv - iv_count[mask], ev - ev_count[mask]) + inner_score[mask] + inter_score[premask][mask])\n",
    "            return res\n",
    "\n",
    "        init_data()\n",
    "        return dfs(0, 0, introvertsCount, extrovertsCount)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxGridHappiness(self, m: int, n: int, introvertsCount: int, extrovertsCount: int) -> int:\n",
    "        T, N, M = 243, 5, 6\n",
    "        # 邻居间的分数\n",
    "        score = [\n",
    "            [0, 0, 0],\n",
    "            [0, -60, -10],\n",
    "            [0, -10, 40],\n",
    "        ]\n",
    "\n",
    "        tot = 3**n\n",
    "        mask_bits = [[0] * N for _ in range(T)]\n",
    "        iv_count, ev_count = [0] * T, [0] * T\n",
    "        inner_score = [0] * T\n",
    "        inter_score = [[0] * T for _ in range(T)]\n",
    "    \n",
    "        def init_data() -> None:\n",
    "            # 计算行内分数\n",
    "            for mask in range(tot):\n",
    "                mask_tmp = mask\n",
    "                for i in range(n):\n",
    "                    x = mask_tmp % 3\n",
    "                    mask_bits[mask][i] = x\n",
    "                    mask_tmp //= 3\n",
    "                    if x == 1:\n",
    "                        iv_count[mask] += 1\n",
    "                        inner_score[mask] += 120\n",
    "                    elif x == 2:\n",
    "                        ev_count[mask] += 1\n",
    "                        inner_score[mask] += 40\n",
    "                    if i > 0:\n",
    "                        inner_score[mask] += score[x][mask_bits[mask][i - 1]]\n",
    "            # 计算行间分数\n",
    "            for i in range(tot):\n",
    "                for j in range(tot):\n",
    "                    for k in range(n):\n",
    "                        inter_score[i][j] += score[mask_bits[i][k]][mask_bits[j][k]]\n",
    "        \n",
    "        @cache\n",
    "        def dfs(row: int, premask: int, iv: int, ev: int) -> int:\n",
    "            if row == m or (iv == 0 and ev == 0):\n",
    "                return 0\n",
    "            \n",
    "            res = 0\n",
    "            for mask in range(tot):\n",
    "                # mask 包含的内向人数不能超过 iv ，外向人数不能超过 ev\n",
    "                if iv_count[mask] > iv or ev_count[mask] > ev:\n",
    "                    continue\n",
    "                res = max(res, dfs(row + 1, mask, iv - iv_count[mask], ev - ev_count[mask]) + inner_score[mask] + inter_score[premask][mask])\n",
    "            return res\n",
    "\n",
    "        init_data()\n",
    "        return dfs(0, 0, introvertsCount, extrovertsCount)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxGridHappiness(self, m: int, n: int, introvertsCount: int, extrovertsCount: int) -> int:\n",
    "        T, N, M = 243, 5, 6\n",
    "        # 邻居间的分数\n",
    "        score = [\n",
    "            [0, 0, 0],\n",
    "            [0, -60, -10],\n",
    "            [0, -10, 40],\n",
    "        ]\n",
    "\n",
    "        tot = 3**n\n",
    "        mask_bits = [[0] * N for _ in range(T)]\n",
    "        iv_count, ev_count = [0] * T, [0] * T\n",
    "        inner_score = [0] * T\n",
    "        inter_score = [[0] * T for _ in range(T)]\n",
    "    \n",
    "        def init_data() -> None:\n",
    "            # 计算行内分数\n",
    "            for mask in range(tot):\n",
    "                mask_tmp = mask\n",
    "                for i in range(n):\n",
    "                    x = mask_tmp % 3\n",
    "                    mask_bits[mask][i] = x\n",
    "                    mask_tmp //= 3\n",
    "                    if x == 1:\n",
    "                        iv_count[mask] += 1\n",
    "                        inner_score[mask] += 120\n",
    "                    elif x == 2:\n",
    "                        ev_count[mask] += 1\n",
    "                        inner_score[mask] += 40\n",
    "                    if i > 0:\n",
    "                        inner_score[mask] += score[x][mask_bits[mask][i - 1]]\n",
    "            # 计算行间分数\n",
    "            for i in range(tot):\n",
    "                for j in range(tot):\n",
    "                    for k in range(n):\n",
    "                        inter_score[i][j] += score[mask_bits[i][k]][mask_bits[j][k]]\n",
    "        \n",
    "        @cache\n",
    "        def dfs(row: int, premask: int, iv: int, ev: int) -> int:\n",
    "            if row == m or (iv == 0 and ev == 0):\n",
    "                return 0\n",
    "            \n",
    "            res = 0\n",
    "            for mask in range(tot):\n",
    "                # mask 包含的内向人数不能超过 iv ，外向人数不能超过 ev\n",
    "                if iv_count[mask] > iv or ev_count[mask] > ev:\n",
    "                    continue\n",
    "                res = max(res, dfs(row + 1, mask, iv - iv_count[mask], ev - ev_count[mask]) + inner_score[mask] + inter_score[premask][mask])\n",
    "            return res\n",
    "\n",
    "        init_data()\n",
    "        return dfs(0, 0, introvertsCount, extrovertsCount)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxGridHappiness(self, m: int, n: int, introvertsCount: int, extrovertsCount: int) -> int:\n",
    "        # dwjs(m,m行状态，m,n)\n",
    "        ret=0\n",
    "        nx=introvertsCount\n",
    "        wx=extrovertsCount\n",
    "        f=3**n\n",
    "        xx=[-1 for _ in range(f)]\n",
    "        #print(n,f)\n",
    "        if n==1:\n",
    "            xx[0]=0\n",
    "            xx[1]=120\n",
    "            xx[2]=40\n",
    "        temp=[0]*n\n",
    "\n",
    "        def dwcx(zt):\n",
    "            yzt=zt\n",
    "            #print('DWCX:',zt,xx[zt])\n",
    "            if xx[yzt]>-1:\n",
    "                return xx[zt]\n",
    "            #print(\"KSJS\")\n",
    "            for i in range(n):\n",
    "                temp[i]=zt%3\n",
    "                zt//=3\n",
    "            #print(temp)\n",
    "            ret=0\n",
    "            if temp[0]==0:\n",
    "                ret=0\n",
    "            elif temp[0]==1:\n",
    "                if temp[1]>0:\n",
    "                    ret=90\n",
    "                else:\n",
    "                    ret=120\n",
    "            else:\n",
    "                if temp[1]>0:\n",
    "                    ret=60\n",
    "                else:\n",
    "                    ret=40\n",
    "            if temp[n-1]==0:\n",
    "                ret+=0\n",
    "            elif temp[n-1]==1:\n",
    "                if temp[n-2]>0:\n",
    "                    ret+=90\n",
    "                else:\n",
    "                    ret+=120\n",
    "            else:\n",
    "                if temp[n-2]>0:\n",
    "                    ret+=60\n",
    "                else:\n",
    "                    ret+=40            \n",
    "\n",
    "            for i in range(1,n-1):\n",
    "                if temp[i]==0:\n",
    "                    continue\n",
    "                elif temp[i]==1:\n",
    "                    ret+=120\n",
    "                    if temp[i-1]>0:\n",
    "                        ret-=30\n",
    "                    if temp[i+1]>0:\n",
    "                        ret-=30\n",
    "                else:\n",
    "                    ret+=40\n",
    "                    if temp[i-1]>0:\n",
    "                        ret+=20\n",
    "                    if temp[i+1]>0:\n",
    "                        ret+=20\n",
    "            xx[yzt]=ret\n",
    "            #print(\"CX\",yzt,ret)\n",
    "            return ret\n",
    "        @cache\n",
    "        def dwfx(zt1,zt2):\n",
    "            ret=0\n",
    "            for i in range(n):\n",
    "                x=zt1%3\n",
    "                y=zt2%3\n",
    "                zt1//=3\n",
    "                zt2//=3\n",
    "                if x==0 or y==0:\n",
    "                    continue\n",
    "                elif x==1:\n",
    "                    if  y==1:\n",
    "                        ret-=60\n",
    "                    else:\n",
    "                        ret-=10\n",
    "                else:\n",
    "                    if  y==1:\n",
    "                        ret-=10\n",
    "                    else:\n",
    "                        ret+=40                    \n",
    "            return ret\n",
    "\n",
    "        @cache\n",
    "        def dwcxzt(nx,wx):\n",
    "            ret=[]\n",
    "            \n",
    "            def xmjs(p,nx,wx,zt):\n",
    "                if p==n:\n",
    "                    ret.append([zt,nx,wx])\n",
    "                    return\n",
    "                xmjs(p+1,nx,wx,zt*3)\n",
    "                if nx>0:\n",
    "                    zt1=zt*3+1\n",
    "                    xmjs(p+1,nx-1,wx,zt1)\n",
    "                if wx>0:\n",
    "                    zt2=zt*3+2\n",
    "                    xmjs(p+1,nx,wx-1,zt2)\n",
    "            xmjs(0,nx,wx,0)\n",
    "            return ret\n",
    "        @cache\n",
    "        def dwjs(id,zt,nx,wx):\n",
    "            if id==m:\n",
    "                return 0\n",
    "            if nx==0 and wx==0:\n",
    "                return 0\n",
    "            #fs1=dwcx(zt)\n",
    "            fs=0\n",
    "            ret=0\n",
    "            kzt=dwcxzt(nx,wx)   #查询所有状态,kzt[状态吗，剩nx,剩wx]\n",
    "            for k in kzt:\n",
    "                #print('ZT=',k,zt)\n",
    "                fs2=dwcx(k[0])      #查询状态下本行分数\n",
    "                fs3=dwfx(zt,k[0])  #查询两行状态下分数\n",
    "                fs4=dwjs(id+1,k[0],k[1],k[2])\n",
    "                fs=fs2+fs3+fs4\n",
    "                #print(fs,fs2,fs3,fs4)\n",
    "                if fs>ret:\n",
    "                    ret=fs\n",
    "            return ret\n",
    "        zt=0\n",
    "        ret=dwjs(0,zt,introvertsCount,extrovertsCount)\n",
    "        #print(xx)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# 三进制状压DP + 预处理\n",
    "class Solution:\n",
    "    def getMaxGridHappiness(self, m: int, n: int, introvertsCount: int, extrovertsCount: int) -> int:\n",
    "\n",
    "        T, N, M = 3**5, 5, 6\n",
    "        INTROVERT, EXTROVERT = 1, 2\n",
    "        IV_SCORE, EV_SCORE = 120, 40\n",
    "        # 邻居间的分数\n",
    "        score = [\n",
    "            [0, 0, 0],\n",
    "            [0, -60, -10],\n",
    "            [0, -10, 40],\n",
    "        ]\n",
    "\n",
    "        tot = 3**n\n",
    "        mask_bits = [[0] * N for _ in range(T)]\n",
    "        iv_count = [0] * T\n",
    "        ev_count = [0] * T\n",
    "        inner_score = [0] * T\n",
    "        inter_score = [[0] * T for _ in range(T)]\n",
    "\n",
    "        def init_data():\n",
    "            # 计算行内分数\n",
    "            for mask in range(tot):\n",
    "                mask_tmp = mask\n",
    "                pre_state = 0\n",
    "                for j in range(n):\n",
    "                    state = mask_tmp % 3\n",
    "                    mask_bits[mask][j] = state\n",
    "                    mask_tmp //= 3\n",
    "                    if state == INTROVERT:\n",
    "                        iv_count[mask] += 1\n",
    "                    elif state == EXTROVERT:\n",
    "                        ev_count[mask] += 1\n",
    "                    inner_score[mask] += score[state][pre_state]\n",
    "                    pre_state = state\n",
    "            # 计算行间影响的分数\n",
    "            for mask in range(tot):\n",
    "                for pre_mask in range(tot):\n",
    "                    for j in range(n):\n",
    "                        inter_score[mask][pre_mask] += score[mask_bits[mask]\n",
    "                                                             [j]][mask_bits[pre_mask][j]]\n",
    "        init_data()\n",
    "\n",
    "        @cache\n",
    "        def dfs(row: int, pre_mask: int, iv: int, ev: int) -> int:\n",
    "            if row == m or (iv | ev) == 0:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for mask in range(tot):\n",
    "                if iv_count[mask] > iv or ev_count[mask] > ev:\n",
    "                    continue\n",
    "                res = max(res, dfs(row + 1, mask, iv - iv_count[mask],  ev - ev_count[mask]) + inner_score[mask] +\n",
    "                          inter_score[mask][pre_mask] + iv_count[mask] * IV_SCORE + ev_count[mask] * EV_SCORE)\n",
    "            return res\n",
    "\n",
    "        ans = dfs(0, 0, introvertsCount, extrovertsCount)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxGridHappiness(\n",
    "        self, m: int, n: int, introvertsCount: int, extrovertsCount: int\n",
    "    ) -> int:\n",
    "        @cache\n",
    "        def dfs(i: int, pre: int, ic: int, ec: int) -> int:\n",
    "            if i == m or (ic == 0 and ec == 0):\n",
    "                return 0\n",
    "            ans = 0\n",
    "            for cur in range(mx):\n",
    "                if ix[cur] <= ic and ex[cur] <= ec:\n",
    "                    a = f[cur] + g[pre][cur]\n",
    "                    b = dfs(i + 1, cur, ic - ix[cur], ec - ex[cur])\n",
    "                    ans = max(ans, a + b)\n",
    "            return ans\n",
    "\n",
    "        mx = pow(3, n)\n",
    "        f = [0] * mx\n",
    "        g = [[0] * mx for _ in range(mx)]\n",
    "        h = [[0, 0, 0], [0, -60, -10], [0, -10, 40]]\n",
    "        bits = [[0] * n for _ in range(mx)]\n",
    "        ix = [0] * mx\n",
    "        ex = [0] * mx\n",
    "        for i in range(mx):\n",
    "            mask = i\n",
    "            for j in range(n):\n",
    "                mask, x = divmod(mask, 3)\n",
    "                bits[i][j] = x\n",
    "                if x == 1:\n",
    "                    ix[i] += 1\n",
    "                    f[i] += 120\n",
    "                elif x == 2:\n",
    "                    ex[i] += 1\n",
    "                    f[i] += 40\n",
    "                if j:\n",
    "                    f[i] += h[x][bits[i][j - 1]]\n",
    "        for i in range(mx):\n",
    "            for j in range(mx):\n",
    "                for k in range(n):\n",
    "                    g[i][j] += h[bits[i][k]][bits[j][k]]\n",
    "        return dfs(0, 0, introvertsCount, extrovertsCount)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxGridHappiness(\n",
    "        self, m: int, n: int, introvertsCount: int, extrovertsCount: int\n",
    "    ) -> int:\n",
    "        @cache\n",
    "        def dfs(i: int, pre: int, ic: int, ec: int) -> int:\n",
    "            if i == m or (ic == 0 and ec == 0):\n",
    "                return 0\n",
    "            ans = 0\n",
    "            for cur in range(mx):\n",
    "                if ix[cur] <= ic and ex[cur] <= ec:\n",
    "                    a = f[cur] + g[pre][cur]\n",
    "                    b = dfs(i + 1, cur, ic - ix[cur], ec - ex[cur])\n",
    "                    ans = max(ans, a + b)\n",
    "            return ans\n",
    "\n",
    "        mx = pow(3, n)\n",
    "        f = [0] * mx\n",
    "        g = [[0] * mx for _ in range(mx)]\n",
    "        h = [[0, 0, 0], [0, -60, -10], [0, -10, 40]]\n",
    "        bits = [[0] * n for _ in range(mx)]\n",
    "        ix = [0] * mx\n",
    "        ex = [0] * mx\n",
    "        for i in range(mx):\n",
    "            mask = i\n",
    "            for j in range(n):\n",
    "                mask, x = divmod(mask, 3)\n",
    "                bits[i][j] = x\n",
    "                if x == 1:\n",
    "                    ix[i] += 1\n",
    "                    f[i] += 120\n",
    "                elif x == 2:\n",
    "                    ex[i] += 1\n",
    "                    f[i] += 40\n",
    "                if j:\n",
    "                    f[i] += h[x][bits[i][j - 1]]\n",
    "        for i in range(mx):\n",
    "            for j in range(mx):\n",
    "                for k in range(n):\n",
    "                    g[i][j] += h[bits[i][k]][bits[j][k]]\n",
    "        return dfs(0, 0, introvertsCount, extrovertsCount)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxGridHappiness(\n",
    "        self, m: int, n: int, introvertsCount: int, extrovertsCount: int\n",
    "    ) -> int:\n",
    "        @cache\n",
    "        def dfs(i: int, pre: int, ic: int, ec: int) -> int:\n",
    "            if i == m or (ic == 0 and ec == 0):\n",
    "                return 0\n",
    "            ans = 0\n",
    "            for cur in range(mx):\n",
    "                if ix[cur] <= ic and ex[cur] <= ec:\n",
    "                    a = f[cur] + g[pre][cur]\n",
    "                    b = dfs(i + 1, cur, ic - ix[cur], ec - ex[cur])\n",
    "                    ans = max(ans, a + b)\n",
    "            return ans\n",
    "\n",
    "        mx = pow(3, n)\n",
    "        f = [0] * mx\n",
    "        g = [[0] * mx for _ in range(mx)]\n",
    "        h = [[0, 0, 0], [0, -60, -10], [0, -10, 40]]\n",
    "        bits = [[0] * n for _ in range(mx)]\n",
    "        ix = [0] * mx\n",
    "        ex = [0] * mx\n",
    "        for i in range(mx):\n",
    "            mask = i\n",
    "            for j in range(n):\n",
    "                mask, x = divmod(mask, 3)\n",
    "                bits[i][j] = x\n",
    "                if x == 1:\n",
    "                    ix[i] += 1\n",
    "                    f[i] += 120\n",
    "                elif x == 2:\n",
    "                    ex[i] += 1\n",
    "                    f[i] += 40\n",
    "                if j:\n",
    "                    f[i] += h[x][bits[i][j - 1]]\n",
    "        for i in range(mx):\n",
    "            for j in range(mx):\n",
    "                for k in range(n):\n",
    "                    g[i][j] += h[bits[i][k]][bits[j][k]]\n",
    "        return dfs(0, 0, introvertsCount, extrovertsCount)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getMaxGridHappiness(self, m: int, n: int, I: int, E: int) -> int:\n",
    "        # 参考 fdvoid0:https://leetcode.cn/problems/maximize-grid-happiness/solutions/2318413/python3dong-tai-gui-hua-di-gui-ji-yi-hua-90h6/\n",
    "\n",
    "        # 我们假设左上角已算好,利用左上角计算当前一个格子的数字\n",
    "        # dfs(idx) 由 dfs(idx-1) 以及idx右侧格子,idx下侧格子, 剩余内向,外向总数 决定\n",
    "        # 所以从右下角开始递归 DFS(第idx个格子, 后续n个格子组, 内向总数, 外向总数)\n",
    "        # (相邻的两个人总共发生的变化)\n",
    "        #  己方格子\\对方格子:空   内            外\n",
    "        #  空                +0   +0            +0 \n",
    "        #  内                +0   2*inL         inL+exL\n",
    "        #  外                +0   inL+exL       2*exL\n",
    "        face2face = [\n",
    "            [0,0,0],\n",
    "            [0,-30*2, -30+20],\n",
    "            [0,-30+20,+20+20]\n",
    "        ]\n",
    "        # 后续n个格子组状态存放在 nxt = [.........]\n",
    "        @cache\n",
    "        def dfs(idx, nxt, I,E):\n",
    "            ans=0\n",
    "            if idx==-1:  #一个格子都不填\n",
    "                return 0\n",
    "            for val in [0,1,2]:\n",
    "                right=nxt[0] if idx%n != n-1 else 0\n",
    "                bottom=nxt[-1] if idx//n != m-1 else 0\n",
    "                face=face2face[val][right]+face2face[val][bottom]\n",
    "                newnxt = (val,)+nxt[:-1]\n",
    "                if val==0:\n",
    "                    ans=max(ans,dfs(idx-1, newnxt, I, E) + face)\n",
    "                elif val==1 and I-1>=0:\n",
    "                    ans=max(ans,120+dfs(idx-1, newnxt, I-1, E) + face)\n",
    "                elif val==2 and E-1>=0:\n",
    "                    ans=max(ans,40+dfs(idx-1, newnxt, I, E-1) + face)\n",
    "            return ans\n",
    "        return dfs(m*n-1, tuple([0]*n), I ,E)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxGridHappiness(self, m, n, I, E):\n",
    "        InG, ExG, InL, ExL = 120, 40, -30, 20\n",
    "        fine = [[0, 0, 0], [0, 2*InL, InL+ExL], [0, InL+ExL, 2*ExL]]\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dp(index, row, I, E):\n",
    "            if index == -1: return 0\n",
    "\n",
    "            R, C, ans = index//n, index%n, []\n",
    "            neibs = [(1, I-1, E, InG), (2, I, E-1, ExG), (0, I, E, 0)]  \n",
    "            \n",
    "            for val, dx, dy, gain in neibs:\n",
    "                tmp = 0\n",
    "                if dx >= 0 and dy >= 0:\n",
    "                    tmp = dp(index-1, (val,) + row[:-1], dx, dy) + gain\n",
    "                    if C < n-1: tmp += fine[val][row[0]]  #右邻居\n",
    "                    if R < m-1: tmp += fine[val][row[-1]] #下邻居\n",
    "                ans.append(tmp)\n",
    "\n",
    "            return max(ans)\n",
    "        \n",
    "        if m < n: m, n = n, m\n",
    "            \n",
    "        return dp(m*n-1, tuple([0]*n), I, E)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxGridHappiness(self, m: int, n: int, introvertsCount: int, extrovertsCount: int) -> int:\n",
    "        adj = [\n",
    "            [0, 0, 0],\n",
    "            [0, -60, -10],\n",
    "            [0, -10, 40]\n",
    "        ]\n",
    "\n",
    "        @cache\n",
    "        def mask2arr(mask):\n",
    "            ret = []\n",
    "\n",
    "            for i in range(n):\n",
    "                ret.append(mask % 3)\n",
    "                mask = mask // 3\n",
    "\n",
    "            return ret\n",
    "\n",
    "        @cache\n",
    "        def innerscore(mask):\n",
    "            arr = mask2arr(mask)\n",
    "\n",
    "            ret = 0\n",
    "            for i in range(n):\n",
    "                x = arr[i]\n",
    "\n",
    "                if x == 1:\n",
    "                    ret += 120\n",
    "                elif x == 2:\n",
    "                    ret += 40\n",
    "\n",
    "                if i > 0:\n",
    "                    ret += adj[arr[i]][arr[i - 1]]\n",
    "\n",
    "            return ret\n",
    "\n",
    "        @cache\n",
    "        def interscore(premask, mask):\n",
    "            a = mask2arr(premask)\n",
    "            b = mask2arr(mask)\n",
    "\n",
    "            ret = 0\n",
    "            for i in range(n):\n",
    "                ret += adj[b[i]][a[i]]\n",
    "\n",
    "            return ret\n",
    "\n",
    "        @cache\n",
    "        def popcount(mask):\n",
    "            arr = mask2arr(mask)\n",
    "\n",
    "            ic = 0\n",
    "            ec = 0\n",
    "            for i in range(n):\n",
    "                if arr[i] == 1:\n",
    "                    ic += 1\n",
    "                elif arr[i] == 2:\n",
    "                    ec += 1\n",
    "\n",
    "            return ic, ec\n",
    "\n",
    "        tot = 3 ** n\n",
    "        @cache\n",
    "        def dp(row, premask, iv, ev):\n",
    "            if row == m:\n",
    "                return 0\n",
    "\n",
    "            if iv == 0 and ev == 0:\n",
    "                return 0\n",
    "\n",
    "            ret = 0\n",
    "\n",
    "            for mask in range(tot):\n",
    "                ic, ec = popcount(mask)\n",
    "\n",
    "                if ic > iv or ec > ev:\n",
    "                    continue\n",
    "\n",
    "                ret = max(\n",
    "                    ret,\n",
    "                    dp(row + 1, mask, iv - ic, ev - ec) + innerscore(mask) + interscore(premask, mask)\n",
    "                )\n",
    "\n",
    "            return ret\n",
    "\n",
    "        return dp(0, 0, introvertsCount, extrovertsCount)\n",
    "        \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxGridHappiness(self, m: int, n: int, introvertsCount: int, extrovertsCount: int) -> int:\n",
    "\n",
    "        def num_to_state(num):\n",
    "            return\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, state, intro, ext):\n",
    "            if i == m*n:\n",
    "                return 0\n",
    "            up = state//w\n",
    "            left = state % 3\n",
    "            res = dfs(i+1, (state-up*w)*3, intro, ext)\n",
    "            if intro:\n",
    "                cur = dfs(i+1, (state-up*w)*3+1, intro-1, ext) + 120\n",
    "                \n",
    "                if i%n:\n",
    "                    if left == 1:\n",
    "                        cur += (-30) - 30\n",
    "                    elif left == 2:\n",
    "                        cur += (-30) + 20\n",
    "      \n",
    "                if up == 1:\n",
    "                    cur += (-30) - 30\n",
    "                elif up == 2:\n",
    "                    cur += (-30) + 20\n",
    "                if cur > res:\n",
    "                    res = cur\n",
    "            if ext:\n",
    "                cur = dfs(i + 1, (state - up * w) * 3 + 2, intro, ext-1) + 40\n",
    "                \n",
    "                if i % n:\n",
    "                    if left == 1:\n",
    "                        cur += 20 - 30\n",
    "                    elif left == 2:\n",
    "                        cur += 20 + 20\n",
    "        \n",
    "                if up == 1:\n",
    "                    cur += 20 - 30\n",
    "                elif up == 2:\n",
    "                    cur += 20 + 20\n",
    "                if cur > res:\n",
    "                    res = cur\n",
    "            return res\n",
    "\n",
    "        w = 3**(n-1)\n",
    "        return dfs(0, 0, introvertsCount, extrovertsCount)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxGridHappiness(self, m: int, n: int, introvertsCount: int, extrovertsCount: int) -> int:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, state, intro, ext):\n",
    "            if i == m * n:\n",
    "                return 0\n",
    "            up = state // w if i // n else 0\n",
    "            left = state % 3 if i % n else 0\n",
    "            res = dfs(i + 1, (state - up * w) * 3, intro, ext)\n",
    "            if intro:\n",
    "                cur = dfs(i + 1, (state - up * w) * 3 + 1, intro - 1, ext) + 120\n",
    "                cur += cross[1][up] + cross[1][left]\n",
    "                if cur > res:\n",
    "                    res = cur\n",
    "            if ext:\n",
    "                cur = dfs(i + 1, (state - up * w) * 3 + 2, intro, ext - 1) + 40\n",
    "                cur += cross[2][up] + cross[2][left]\n",
    "                if cur > res:\n",
    "                    res = cur\n",
    "            return res\n",
    "\n",
    "        w = 3 ** (n - 1)\n",
    "        cross = [[0, 0, 0], [0, -60, -10], [0, -10, 40]]\n",
    "        return dfs(0, 0, introvertsCount, extrovertsCount)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxGridHappiness(self, m: int, n: int, introvertsCount: int, extrovertsCount: int) -> int:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, state, intro, ext):\n",
    "            if i == m * n:\n",
    "                return 0\n",
    "            up = state // w if i // n else 0\n",
    "            left = state % 3 if i % n else 0\n",
    "            res = dfs(i + 1, (state - up * w) * 3, intro, ext)\n",
    "            if intro:\n",
    "                cur = dfs(i + 1, (state - up * w) * 3 + 1, intro - 1, ext) + 120\n",
    "                if left == 1:\n",
    "                    cur += (-30) - 30\n",
    "                elif left == 2:\n",
    "                    cur += (-30) + 20\n",
    "                if up == 1:\n",
    "                    cur += (-30) - 30\n",
    "                elif up == 2:\n",
    "                    cur += (-30) + 20\n",
    "                if cur > res:\n",
    "                    res = cur\n",
    "            if ext:\n",
    "                cur = dfs(i + 1, (state - up * w) * 3 + 2, intro, ext - 1) + 40\n",
    "                if left == 1:\n",
    "                    cur += 20 - 30\n",
    "                elif left == 2:\n",
    "                    cur += 20 + 20\n",
    "                if up == 1:\n",
    "                    cur += 20 - 30\n",
    "                elif up == 2:\n",
    "                    cur += 20 + 20\n",
    "                if cur > res:\n",
    "                    res = cur\n",
    "            return res\n",
    "\n",
    "        w = 3 ** (n - 1)\n",
    "        return dfs(0, 0, introvertsCount, extrovertsCount)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.m, self.n = 0, 0\n",
    "\n",
    "        # 压缩状态的定义\n",
    "        self.masks = {}  # 记录每一个状态的三进制表示\n",
    "        self.truncate = {}  # 下一位的三种情况\n",
    "\n",
    "    def getMaxGridHappiness(self, m: int, n: int, introvertsCount: int, extrovertsCount: int) -> int:\n",
    "        self.m, self.n = m, n\n",
    "\n",
    "        # 预处理状态压缩的情况\n",
    "        highest = 3 ** (n - 1)\n",
    "        for mask in range(3 ** n):\n",
    "            mask_tmp = mask\n",
    "            bits = []\n",
    "            for i in range(n):\n",
    "                bits.append(mask_tmp % 3)\n",
    "                mask_tmp //= 3\n",
    "            # 与方法一不同的是，这里需要反过来存储，这样 [0] 对应最高位，[n-1] 对应最低位\n",
    "            self.masks[mask] = bits[::-1]\n",
    "            self.truncate[mask] = [mask % highest * 3, mask % highest * 3 + 1, mask % highest * 3 + 2]\n",
    "\n",
    "        return self.dfs(0, 0, introvertsCount, extrovertsCount)\n",
    "\n",
    "    @lru_cache(None)\n",
    "    def dfs(self, pos: int, borderline: int, nx: int, wx: int):\n",
    "        \"\"\"深度优先遍历：记忆化递归\"\"\"\n",
    "        # 边界条件：如果已经分配到结尾，或已经分配了的所有人\n",
    "        if pos == self.m * self.n or nx + wx == 0:\n",
    "            return 0\n",
    "\n",
    "        # 什么都不做\n",
    "        best = self.dfs(pos + 1, self.truncate[borderline][0], nx, wx)\n",
    "        # 放一个内向的人\n",
    "        if nx > 0:\n",
    "            best = max(best, 120 + self.count(1, self.masks[borderline][0]) \\\n",
    "                       + (0 if pos % self.n == 0 else self.count(1, self.masks[borderline][self.n - 1])) \\\n",
    "                       + self.dfs(pos + 1, self.truncate[borderline][1], nx - 1, wx))\n",
    "        # 放一个外向的人\n",
    "        if wx > 0:\n",
    "            best = max(best, 40 + self.count(2, self.masks[borderline][0]) \\\n",
    "                       + (0 if pos % self.n == 0 else self.count(2, self.masks[borderline][self.n - 1])) \\\n",
    "                       + self.dfs(pos + 1, self.truncate[borderline][2], nx, wx - 1))\n",
    "\n",
    "        return best\n",
    "\n",
    "    @staticmethod\n",
    "    def count(x, y):\n",
    "        \"\"\"计算相邻的房屋x和房屋y之间的收益增量\"\"\"\n",
    "        if x == 0 or y == 0:  # 有一个空房\n",
    "            return 0\n",
    "        elif x == 1 and y == 1:  # 两个内向的人\n",
    "            return -60\n",
    "        elif x == 2 and y == 2:  # 两个外向的人\n",
    "            return 40\n",
    "        else:  # 一个外向的人和一个内向的人\n",
    "            return -10\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxGridHappiness(self, m: int, n:int, introvertsCount:int, extrovertsCount: int) ->int:\n",
    "        T,N,M = 243, 5, 6\n",
    "        score=[\n",
    "            [0,0,0],\n",
    "            [0,-60,-10],\n",
    "            [0,-10,40],\n",
    "        ]\n",
    "        tot = 3 ** n\n",
    "        p = [1]\n",
    "        for i in range(1,n):\n",
    "            p.append(p[-1] * 3)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(pos:int, mask:int, iv:int, ev:int)->int:\n",
    "            if pos == n*m or (iv==0 and ev==0):\n",
    "                return 0\n",
    "            res= 0\n",
    "            up, left = mask // p[n-1], mask % 3\n",
    "            if pos % n == 0:\n",
    "                left = 0\n",
    "            for i in range(3):\n",
    "                if (i==1 and iv == 0) or (i==2 and ev == 0):\n",
    "                    continue\n",
    "                next_mask = mask % p[n-1] * 3 + i\n",
    "                score_num =dfs(pos+1, next_mask, iv - (i==1), ev - (i==2)) +score[up][i] +score[left][i]\n",
    "                if i==1:\n",
    "                    score_num +=120\n",
    "                elif i==2:\n",
    "                    score_num += 40\n",
    "                res = max(res, score_num)\n",
    "            return res\n",
    "        \n",
    "        return dfs(0,0,introvertsCount,extrovertsCount)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# 轮廓线DP\n",
    "\n",
    "class Solution:\n",
    "    def getMaxGridHappiness(self, m: int, n: int, introvertsCount: int, extrovertsCount: int) -> int:\n",
    "\n",
    "        neigh_score = [\n",
    "            [0, 0, 0],\n",
    "            [0, -60, -10],\n",
    "            [0, -10, 40],\n",
    "        ]\n",
    "        state_score = [0, 120, 40]\n",
    "\n",
    "        @cache\n",
    "        def dfs(pos: int, mask: int, iv: int, ev: int) -> int:\n",
    "            if pos == m * n or (iv | ev) == 0:\n",
    "                return 0\n",
    "            up, left = mask // 3**(n-1), mask % 3\n",
    "            # 如果是第一列，则左边的网格状态设置为0\n",
    "            if pos % n == 0:\n",
    "                left = 0\n",
    "            res = 0\n",
    "            for state in range(3):\n",
    "                if state == 1 and iv == 0 or state == 2 and ev == 0:\n",
    "                    continue\n",
    "                res = max(res, dfs(pos + 1, mask % (3 ** (n-1)) * 3 + state, iv - (state & 1), ev - (state >>\n",
    "                          1)) + neigh_score[state][up] + neigh_score[state][left] + state_score[state])\n",
    "            return res\n",
    "\n",
    "        ans = dfs(0, 0, introvertsCount, extrovertsCount)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxGridHappiness(self, m: int, n: int, introvertsCount: int, extrovertsCount: int) -> int:\n",
    "\n",
    "        @cache\n",
    "        def f(i, st, pin, pex):\n",
    "            if i == m*n or pin == 0 and pex == 0:\n",
    "                return 0\n",
    "            res = f(i+1, st[1:]+'N', pin, pex)\n",
    "            if pin > 0:\n",
    "                v = 120\n",
    "                for p in [st[0], (st[-1] if i % n != 0 else 'N')]:\n",
    "                    if p == 'I':\n",
    "                        v -= 60\n",
    "                    elif p == 'E':\n",
    "                        v -= 10\n",
    "                res = max(res, f(i+1, st[1:]+'I', pin-1, pex)+v)\n",
    "            if pex > 0:\n",
    "                v = 40\n",
    "                for p in [st[0], (st[-1] if i % n != 0 else 'N')]:\n",
    "                    if p == 'I':\n",
    "                        v -= 10\n",
    "                    elif p == 'E':\n",
    "                        v += 40\n",
    "                res = max(res, f(i+1, st[1:]+'E', pin, pex-1)+v)\n",
    "            return res\n",
    "        \n",
    "        return f(0, 'N'*n, introvertsCount, extrovertsCount)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxGridHappiness(self, m: int, n: int, introvertsCount: int, extrovertsCount: int) -> int:\n",
    "        def c(a, b):\n",
    "            if a == '0' or b == '0':return 0\n",
    "            elif a == '1' and b == '1':return -60\n",
    "            elif a == '2' and b == '2':return 40\n",
    "            return -10\n",
    "\n",
    "        @cache\n",
    "        def dfs(p, s, ic, ec):\n",
    "            if ic < 0 or ec < 0:return -inf\n",
    "            elif ic + ec == 0 or p == m * n:return 0\n",
    "            else: return max(dfs(p + 1, s[1:] + '0', ic, ec),\n",
    "                    dfs(p + 1, s[1:] + '1', ic - 1, ec) + 120 + c('1', s[0]) + (c('1', s[-1]) if p % n else 0),\n",
    "                    dfs(p + 1, s[1:] + '2', ic, ec - 1) + 40 + c('2', s[0]) + (c('2', s[-1]) if p % n else 0)\n",
    "                )\n",
    "        return dfs(0, '0' * n, introvertsCount, extrovertsCount)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxGridHappiness(self, m: int, n: int, introvertsCount: int, extrovertsCount: int) -> int:\n",
    "        def c(a, b):\n",
    "            if a == '0' or b == '0':\n",
    "                return 0\n",
    "            elif a == '1' and b == '1':\n",
    "                return -60\n",
    "            elif a == '2' and b == '2':\n",
    "                return 40\n",
    "            return -10\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(p, s, ic, ec):\n",
    "            if ic < 0 or ec < 0:\n",
    "                return -inf\n",
    "            elif ic + ec == 0 or p == m * n:\n",
    "                return 0\n",
    "            else:\n",
    "                a = max(\n",
    "                    dfs(p + 1, s[1:] + '0', ic, ec),\n",
    "                    dfs(p + 1, s[1:] + '1', ic - 1, ec) + 120 + c('1', s[0]) + (c('1', s[-1]) if p % n else 0),\n",
    "                    dfs(p + 1, s[1:] + '2', ic, ec - 1) + 40 + c('2', s[0]) + (c('2', s[-1]) if p % n else 0)\n",
    "                )\n",
    "                return a\n",
    "\n",
    "        v = dfs(0, '0' * n, introvertsCount, extrovertsCount)\n",
    "        return v"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
